package code.oldCode.feishuSpecializedTraining.dynamic;

/**
 * @author 26029
 * @date 2025/3/28
 * @description
 */
public class MyDP10 {
    // 1035. 不相交的线
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 1 <= nums1.length, nums2.length <= 500
        int len1 = nums1.length, len2 = nums2.length;
        // 和找最长公共子序列一样
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (nums1[i - 1] == nums2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[len1][len2];
    }

    // 53. 最大子数组和
    public int maxSubArray(int[] nums) {
        // 1 <= nums.length <= 105
        int len = nums.length;
        // dp[i]表示以i结尾的最大子数组和
        int[] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < len; i++) {
            if (dp[i - 1] >= 0)
                dp[i] = dp[i - 1] + nums[i];
            else
                dp[i] = nums[i];
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    // 392. 判断子序列
    public boolean isSubsequence(String s, String t) {
        // 0 <= s.length <= 100 0 <= t.length <= 10^4
        if (s.isEmpty())
            return true;
        if (t.isEmpty())
            return false;
        // 直观做法
        int slen = s.length(), tlen = t.length();
        int spos = 0, tpos = 0;
        while (tpos < tlen && spos < slen) {
            if (t.charAt(tpos) == s.charAt(spos)) {
                spos++;
            }
            tpos++;
        }
        return spos == slen;
    }

    public boolean isSubsequence_dp(String s, String t) {
        // 0 <= s.length <= 100 0 <= t.length <= 10^4
        // 两个字符串都只由小写字符组成
        if (s.isEmpty())
            return true;
        if (t.isEmpty())
            return false;
        // DP做法 dp[i][j]表示字符串t的第i个位置的字符后的字符j第一次出现的位置
        // 优势在于，建立起dp后，每次查找都只用O(s.len)，而不是O(s.len + t.len)
        int slen = s.length(), tlen = t.length();
        int[][] dp = new int[tlen + 1][26];
        // dp[i][j] = char == j ? i : dp[i+1][j]
        for (int j = 0; j < 26; j++) {
            dp[tlen][j] = tlen; // =tlen表示没有
        }
        for (int i = tlen - 1; i >= 0; i--) {
            char c = t.charAt(i);
            for (int j = 0; j < 26; j++) {
                if (c - 'a' == j)
                    dp[i][j] = i;
                else
                    dp[i][j] = dp[i + 1][j];
            }
        }
        // 在s中找
        int nextPos = 0;
        for (int i = 0; i < slen; i++) {
            int temp = dp[nextPos][s.charAt(i) - 'a'];
            if (temp == tlen)
                return false;
            nextPos = temp + 1;
        }
        return true;
    }
}
